Simulating the dynamics of rigid bodies is important for many applications such as, for example, virtual reality devices, simulators and computer games. To be realistic, the simulation takes into account of the interaction of the bodies through contacts such as collisions and connections. For example, if a video game character was an articulated body with arms and legs and a scene involved that character moving, it would not be realistic if the character's forearm temporarily separated from the character's upper arm at the elbow during a body movement. Thus, a simulation process done by simulator hardware or a programmable system programmed according to simulation instructions (e.g., software, codes, etc.) might operate according to general principles that a designer deems are necessary to result in realistic simulations. For example, a designer might deem that body parts attached at joints shall remain attached, that any moving part be subject to friction or not, that parts have weight and are subject to gravity, etc.
It should be understood that for different applications, different general principles might be in play. For example, for a video game simulating the interaction of sports team players, such as American football, soccer, basketball, etc., some effects that might be present in an actual sporting event do not need to be considered, such as air friction, while in other simulations, such as a simulation of a falling body or a diver diving into water, friction at the surface of the body might be taken into account. That said, once the designer settles on what general principles are needed or desirable to provide the realistic simulation, a task of the simulator is to compute the dynamics taking into account those general principles.
Because “realism” is often subjective and people are typically much better that computer in determining how realistic an animation appears, the reader should understand that “realistic” simulation may refer less to what is perceived by a particular set of individuals as being a realistic simulation and refer more to the simulation processes that comply with the general principles that the designer indicates as being representative of realism. In a very specific example, a designer might determine, possibly by some process not fully described herein, that realistic simulation occurs, for that designer's purposes, if each moving object in a scene is represented by a finite number of rigid bodies having mass and those rigid bodies move consistent with (at least approximations of) rules of physics such as (1) inertia, (2) acceleration occurring when a force is applied to a body wherein the acceleration is equal to the force divided by the mass, (3) two rigid bodies will not simultaneously occupy the same space, (4) bodies in the scene not attached to, or resting on, any other body will fall “down”, and so on. It is the role of the simulator to simulate consistent with those general principles, hopefully to provide something that many will consider realistic, but a simulator should not be considered outside of the present definition of a simulator because someone might subjectively determine that its simulations are not realistic looking.
Known Approaches to Rigid-Body Simulation
Many approaches to simulating the interaction of rigid bodies are known. These include constraint-based methods, penalty-based methods, impulse-based methods, collision synchronisation and hybrid methods.
With constraint-based rigid body dynamics simulation, the simulator considers a set of rigid bodies and the forces incident on those bodies to determine how those bodies move from one state to the next (e.g., from one point in time represented by one image of the scene containing those bodies to another point in time represented by a later image of the scene, wherein the sequence of scenes can be displayed in order, to show animation of those bodies). Where there are constraints on bodies, additional forces (constraint reaction forces) are introduced into the system to ensure that the rigid bodies comply with physical constraints on their motion resulting from the interaction of the bodies (for example physical constraints resulting from a collision between bodies or physical constraints resulting from a connection between bodies). The constraint reaction forces may be transient, for example if bodies collide and bounce apart, or they may be persistent, for example if a body rests on another body.
In computer simulation of rigid body dynamics, the movement of the rigid bodies is calculated at discrete times (for example times defined by the frame rate of the display device upon which the positions of the bodies are to be displayed), with the result that each calculation needs to take account of the movement of the bodies and the interaction of the bodies within the predetermined time period since the last calculation (commonly referred to as the “time step”). Simulation is carried out to model changes to the position, velocity and acceleration of the bodies caused by interactions between the bodies within the time step. A particular problem is to prevent bodies from simultaneously occupying the same space at the same time (known as object penetration) by calculating non-penetration constraint forces to keep the objects apart.
Known rigid body constraint-based simulations are either acceleration-based or velocity-based, imposing constraints on the velocity or acceleration of the bodies, respectively and calculating the constraint reaction forces necessary to ensure that the bodies comply with those constraints. The most popular type of constraint-based simulation is velocity-based. Examples of velocity-based methods are described for example in Baraff, D., “Fast Contact Force Computation for Nonpenetrating Rigid Bodies”, Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH '94, pp. 23-34 (1994) (hereinafter [Baraff94]”) and Baraff, D., “Linear-Time Dynamics Using Lagrange Multipliers”, Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH '96, pp. 137-146 (1996) (hereinafter [Baraff96]”).
In velocity-based constraint systems, constraints are imposed upon the velocities of interacting rigid bodies at the time the bodies collide, and the constraint reaction forces that are required to maintain the velocities of the bodies within the defined constraints are calculated.
Typically, an equation containing Lagrange multipliers describing the constraint reaction forces is evaluated. Such an equation has the form shown in Equation (1) (see, for example [Baraff94] and [Baraff96]):JM−1JTλ≧c  (1)where:                J is a Jacobian matrix for all contacts between all bodies in the simulation        M−1 is the inverse of the mass matrix for all bodies        λ is a vector of Lagrange multipliers of the system        C is a vector of the defined velocity constraints        JTλ are the unknown constraint reaction forces acting on the bodies to ensure that the velocities of the bodies satisfy the velocity constraints        
Evaluating Equation (1) above results in the calculation of JTλ defining the constraint reaction forces acting on the bodies to ensure that the bodies' velocities comply with the defined velocity constraints. Following calculation of the constraint reaction forces, the acceleration of each body is calculated using Equation (2) derived from the well-known equations in physics, F=ma, where a is the acceleration of the rigid body, Fext is the known external forces acting on the rigid body (that is, non-constraint forces such as gravity and forces resulting from propulsion simulation, etc.), and m is the individual mass of the rigid body.
                    a        =                                                            J                T                            ⁢                              λ                _                                      +                          F              ext                                m                                    (        2        )            
After calculating the acceleration of each body, the velocity of each body is calculated as follows:vt+1=vt+a.dt  (3)where:                vt+1 is the velocity of the body at time t+1        vt is velocity of the body at time t        dt is the time step duration        
Finally, after calculating the velocity of each body, the position of each body is calculated using Equation (4), where xt+1 is the position of the body at time t+1 and xt is the position of the body at time t.xt+1=xt+vt+1.dt  (4)
The approach above suffers from a number of problems, however.
Firstly, the Jacobian matrix J is a very large matrix, because each row contains parameters for only one constraint (for example, one contact) between one pair of bodies. In addition, in scalar format, three rows are necessary for every constraint, and six columns are necessary for every body. As a result, for even a moderately complex system, J can be of a very large size. Calculating the transpose of J is therefore both computationally expensive and memory expensive, even though the calculation itself is straightforward. Further, the memory storage and computation time requirements increase in proportion to the square of the number of constraints represented by J. Evaluation of the transpose of J is therefore particularly problematic for computer game consoles which typically do not provide extensive processing capability or extensive memory.
Secondly, the approach requires all of the equations above to be evaluated, and further requires the evaluation to be carried out in a specific order. More particularly, forces have to be calculated by evaluating Equation (1), then accelerations have to be calculated using the determined forces by evaluating Equation (2), then velocities have to be calculated using the determined accelerations by evaluating Equation (3), and finally positions have to be calculated using the determined velocities by evaluating Equation (4). Not only is this restrictive, but it is also time-consuming.
Thirdly, errors in the calculated positions of the bodies often occur. This is because the velocity constraint applied to the velocity of the two bodies is that (VA−VB).n≧0; that is the difference between the velocities of the bodies in a normal direction (perpendicular) to the contact plane is not less than zero in order to prevent the bodies moving closer together. However, this constraint is only valid at the instant in time when the bodies touch—not before when the bodies are apart and not after when the bodies are penetrating. Accordingly, if the instant in time at which the body dynamic equations are evaluated does not correspond exactly to the instant in time at which the bodies touch, then the contact forces calculated by evaluating the equations above cause the bodies to stop and suspend in space with a gap therebetween or cause the bodies to stop with one body penetrating the other.
It is known to solve this position error by subsequently adjusting the positions of the bodies to remove the error. However, not only does this add another step to the computation (increasing the number of processing operations and the processing time), but the movement of the bodies to their corrected positions imparts a velocity to the bodies which results in subsequent errors in the dynamics of the bodies.
Improved simulation was sought to overcome these difficulties.